Top K Numbers介紹大綱:

《上篇》

• 介紹Binary Heap(二元堆積)的結構與特性
• Binary Heap與陣列的關係

《中篇》

• Binary Heap種類
• Heap Sort: 了解什麼是heapify，以及heapify如何利用binary heap實現陣列排序

《下篇》
-Top K Numbers Pattern介紹與應用題型

昨天介紹了Binary Heap，今天要來看看如何使用Binary Heap對陣列進行排序。

首先，我們要知道Binary Heap(二元堆積)分為兩種(如下圖):

1. max-heap(最大堆積): parent > child
   就是在heap頂端的數字為所有陣列中最大值，由上往下排序，數字從最大開始遞減。
2. min-heap(最小堆積): child > parent
   反之，就是max-heap排序方式的相反，最小的數字在最頂端。
   

了解max-heap跟min-heap，可以知道heap是利用資料結構進行資料排序方式。
所謂的排序，就是讓無序的Binary Tree，經過Heap Sort後，變成max-heap 或是 min-heap，這個過程稱為"Heapify"。

假設給定一個未排序的陣列(如下圖左側)，而陣列對應的heap結構(如下圖右側)

Heap Sort執行步驟如下:
步驟一. 根據陣列中的元素，建立一個max-heap(最大堆積)
(或 min-heap(最小堆積)，這邊先以max-heap(最大堆積)進行舉例)

步驟2. max-heap排序好後，移除最大的數字，也就是root(根節點)，並把移除的數字放進sorted array中。

在重新heapify的過程中，已經被移除的根節點(root)數字9，在陣列中不會再移動。

重複以上步驟，直到heap中所有的node都被放進sorted array後，就完成heap sort囉!

Reference:

• https://www.youtube.com/watch?v=2DmK_H7IdTo
• https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-binary-heap-ec47ca7aebac
• https://medium.com/starbugs/%E4%BE%86%E5%BE%81%E6%9C%8D%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E5%90%A7-%E6%90%9E%E6%87%82-binary-heap-%E7%9A%84%E6%8E%92%E5%BA%8F%E5%8E%9F%E7%90%86-96768ea30d3f